package com.zklh.leetcode.other.problem104;

import java.util.LinkedList;
import java.util.Queue;

class Solution2 {

    public int maxDepth(TreeNode root) {
        int maxDepth = 0;
        if(root == null){
            return maxDepth;
        }
        // 用于存储访问过的节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 指向当前访问的节点
        TreeNode nowNode = root;
        // 用于接收栈顶元素
        TreeNode topNode = null;
        // 当前访问的深度
        int depth = 0;
        do{
            if(nowNode != null){
                queue.add(nowNode);
                depth++;
                nowNode = nowNode.left;
                nowNode.val=depth;
            }else{// 当前节点为空, 需要抛出栈顶, 栈顶保存了拐点
                // 当抛出的时候 应该更新当前深度为栈元素个数
                depth=queue.size();
                maxDepth = depth > maxDepth ? depth : maxDepth;

                topNode = queue.poll();
                if(topNode == null){
                    break;
                }
                depth=topNode.val;
                nowNode = topNode.right;
            }
        }while(true);
        return  maxDepth;
    }

}
